#define _CRT_SECURE_NO_WARNINGS
//#include <iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int n;
//int a[N];
//void insert_sort()
//{
//	for (int i = 2; i <= n; i++) 
//	{
//		int key = a[i];
//		int j = i - 1;
//		while (j >= 1 && a[j] > key)
//		{
//			a[j + 1] = a[j];
//			j--;
//		}
//		a[j + 1] = key;
//	}
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	insert_sort();
//	for (int i = 1; i <= n; i++) cout << a[i] << " ";
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N];
//int n;
//void select_sort()
//{
//	for (int i = 1; i < n; i++)
//	{
//		int pos = i;
//		for (int j = i; j <= n; j++)
//		{
//			if (a[j] < a[pos])
//				pos = j;
//		}
//		swap(a[i], a[pos]);
//	}
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	select_sort();
//	for (int i = 1; i <= n; i++) cout << a[i] << " ";
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N];
//int n;
//void bobble_sort()
//{
//	for (int i = 1; i < n; i++)
//	{
//		int flag = 0;
//		for (int j = 1; j < n - i + 1; j++)
//		{
//			if (a[j] > a[j + 1])
//			{
//				swap(a[j], a[j + 1]);
//				flag = 1;
//			}
//		}
//		if (flag == 0) return;
//	}
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	bobble_sort();
//	for (int i = 1; i <= n; i++) cout << a[i] << " ";
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N];
//int n;
//void down(int p,int l)
//{
//	int c = p * 2;
//	while (c <= l)
//	{
//		if(c + 1 <= l&& a[c + 1] > a[c]) c++;
//		if(a[p] >= a[c]) return; 
//		swap(a[p], a[c]);
//		p = c;
//		c = p * 2;
//	}
//}
//void Heap_sort()
//{
//	for (int i = n / 2; i >= 1; i--)
//	{
//		down(i, n);
//	}
//	for (int i = n; i > 1; i--)
//	{
//		swap(a[1], a[i]);
//		down(1, i-1);
//	}
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	Heap_sort();
//	for (int i = 1; i <= n; i++) cout << a[i] << " ";
//	return 0;
//}
//#include<iostream>
//#include<ctime>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N];
//int n;
//void quick_sort(int left,int right)
//{
//	if (left >= right) return;
//	int r = a[rand() % (right - left + 1) + left];
//	int j = left - 1, i = left, k = right+1;
//	while(i<k)
//	{
//		if (a[i] < r) swap(a[++j] , a[i++]);
//		else if (a[i] == r) i++;
//		else swap(a[i] , a[--k]);
//	}
//	quick_sort(left, j);
//	quick_sort(k, right);
//}
//int main()
//{
//	srand((unsigned)time(NULL));
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	quick_sort(1,n);
//	for (int i = 1; i <= n; i++) cout << a[i] << " ";
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N],tmp[N];
//int n;
//void merge_sort(int l,int r)
//{
//	if (l >= r) return;
//	int m = (l + r) >> 1;
//	merge_sort(l, m);
//	merge_sort(m+1, r);
//	int i = l, j = m+1, k = l;
//	while (i <= m && j <= r)
//	{
//		if (a[i] < a[j]) tmp[k++] = a[i++];
//		else tmp[k++] = a[j++];
//	}
//	while (i <= m) tmp[k++] = a[i++];
//	while (j <= r) tmp[k++] = a[j++];
//	for (int i = l; i <= r; i++)
//	{
//		a[i] = tmp[i];
//	}
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	merge_sort(1,n);
//	for (int i = 1; i <= n; i++) cout << a[i] << " ";
//	return 0;
//}
//#include<iostream>
//using namespace std;
//int main()
//{
//	int n,a;
//	cin >> n;
//	for (int i = n; i>=0; i--)
//	{
//		cin >> a;
//		if (i != n && a > 0) cout << "+";
//		if (a < 0) cout << "-";
//		if (a == 0) continue;
//		a = abs(a);
//		if (a != 1||(a==1&&i==0)) cout << a;
//		if (i == 1) cout << "x";
//		else if (i > 1) cout << "x^" << i;
//	}
//	return 0;
//}
//#include<iostream>
//using namespace std;
//int a[15][15];
//int x[4] = {0,1,0,-1};
//int y[4] = { 1,0,-1,0 };
//int pos;
//int main()
//{
//	int n; cin >> n;
//	int cnt = 1, i = 1, j = 1;
//	while (cnt <= n*n)
//	{
//		a[i][j] = cnt;
//		int p=i+x[pos], q= j+y[pos];
//		if (p > n || p<1 || q>n || q < 1 || a[p][q])
//		{
//			pos = (pos + 1) % 4;
//			p = i + x[pos], q = j + y[pos];
//		}
//		i = p, j = q;
//		cnt++;
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= n; j++)
//		{
//			printf("%3d", a[i][j]);
//		}
//		printf("\n");
//	}
//}
//#include<iostream>
//#include<algorithm>
//#include<string>
//using namespace std;
//string s, ret;
//int p1, p2, p3;
//void fun(int x)
//{
//	string tmp;
//	int a = s[x - 1], b = s[x + 1];
//	for (char t = a + 1; t < b; t++)
//	{
//		char p = t;
//		if (p1 == 2) p = toupper(p);
//		if (p1 == 3) p = '*';
//		for (int i = 1; i <= p2; i++) tmp += p;
//	}
//	if (p3 == 2) reverse(tmp.begin(), tmp.end());
//	ret += tmp;
//}
//bool is(int i)
//{
//	if ((isalpha(s[i - 1]) && isalpha(s[i + 1])) || (isdigit(s[i - 1]) && isdigit(s[i + 1])))
//		return true;
//	return false;
//}
//int main()
//{
//	 cin >> p1 >> p2 >> p3;
//	 cin >> s;
//	 int n = s.size();
//	 for (int i = 0; i < s.size(); i++)
//	 {
//		 if (s[i] != '-' || i == 0 || i == n - 1) ret += s[i];
//		 else if (s[i - 1] < s[i + 1] && is(i)) fun(i);
//		 else ret += s[i];
//	 }
//	 cout << ret << endl;
//	 return 0;
//}
//#include<iostream>
//using namespace std;
//string s1, s2;
//const int N = 510;
//int a[N], b[N], c[N];
//int lc;
//int main()
//{
//	cin >> s1 >> s2;
//	for (int i = 0; i < s1.size(); i++) a[s1.size() - 1 - i] = s1[i]-'0';
//	for (int i = 0; i < s2.size(); i++) b[s2.size() - 1 - i] = s2[i]-'0';
//	lc = max(s2.size() ,s1.size());
//	for (int i = 0; i < lc; i++)
//	{
//		c[i] += a[i] + b[i];
//		c[i + 1] += c[i] / 10;
//		c[i] %= 10;
//		if (c[lc]) lc++;
//	}
//	for (int i = lc-1; i >= 0; i--)
//	{
//		cout << c[i];
//	}
//	return 0;
//}
//#include<iostream>
//using namespace std;
//string s1, s2;
//const int N = 1e5 + 10;
//int a[N], b[N], c[N];
//int la, lb,lc;
//int main()
//{
//	cin >> s1 >> s2;
//	if (s1.size() < s2.size()) {
//		swap(s1, s2);
//		cout << '-';
//	}
//	else if (s1.size() == s2.size() && s1 < s2) {
//		swap(s1, s2);
//		cout << '-';
//	}
//	for (int i = 0; i < s1.size(); i++) a[s1.size() - 1 - i] = s1[i] - '0';
//	for (int i = 0; i < s2.size(); i++) b[s2.size() - 1 - i] = s2[i]-'0';
//	lc = max( s1.size(),s2.size());
//	for (int i = 0; i < lc; i++)
//	{
//		c[i] += a[i] - b[i];
//		if (c[i] < 0) {
//			c[i + 1]--;
//			c[i] += 10;
//		}
//	}
//	while (lc > 1 && c[lc-1] == 0) lc--;
//	for (int i = lc-1; i >= 0; i--)
//	{
//		cout << c[i];
//	}
//	return 0;
//}